2022 Computer Algorithm                 < No.6 회문 암호>                    Prof. Zoh Q.

회문 암호

[문제]  어떤 문자열에 암호를 심어서 보내려고 한다. 발송된 문자열에서 숨어있는 암호는 해당 문자열의 부순서(subsequence)중에서 가장 긴 회문(palindrome) 순서로 구성되는 문자열이다.  먼저 부순서(subsequence)부터 설명을 한다. 어떤 서열 [eqn: s_i]의 부순서란 이 서열의 부분집합 중에서 [eqn: s_i]의 index가 증가되는 순서로 추출된 순서를 의미한다. 아래 예를 들어서 설명해보자. 만일 S=“mygamebox” 문자열에서 가능한 부순서들은 mabx, mybox, gebo, yamex, gamebox 등이다. 만일 S의 길이가 [eqn: l]이라고 한다면 가능한 부순서 문자열의 개수는 [eqn: 2^l -1]까지 가능하다.

그런데 우리는 발송된 문자열에서 진짜 암호 코드는 그 부순서 문자열 중에서 가장 긴 길이의 회문(longest palindrome)이다. 여러분은 바로 이것을 찾아야 한다. 만일 같은 길이의 회문이라면 사전식 순서로 볼 때 가장 “빠른”것이 유일한 정답이 된다. 만일 문자열이 아래와 같다면

mybagnxaamnaevanratknyaubka

Secret Code = bananaeananab

암호 코드는 bananaeananab가 된다. 현장에서는 회문의 중첩 부분을 암호 코드로 사용한다. 즉 이 경우에는 “banana”가 될 것이다. 이번 문제에서는 전체 회문 부순서를 그대로 다룬다.

[입출력]  입력 파일 stdin 의 첫 줄에 underbar ‘_’와 영문 소문자로만 이루어진 문자열 S가 주어진다. 단 그 길이는 [eqn: 10 LEQ ``|S``| LEQ 1,000] 이다.  여러분은 S의 부순서 중에서 회문이면서 가장 긴 것을 찾아서 문자열로 출력해야 한다. 만일 같은 길이의 부순서가 하나 이상일 경우에는 사전식(Lexicigraphical) 으로 가장 빠른 하나의  문자열을 찾아서 출력해야 한다.

[예제]

stdin	stdout
abcdefghijklmn	a
abcdefghijkflmn	fgf
sometime_summer_time	ei_mm_ie
system_computer_language_intelligence	ecelngagnlece

[제한조건] 프로그램 이름은 code.{c,cpp,java,py}이며 제출 허용 횟수는 15회이다. 데이터 당 제한시간은 최대 1초이다. 문자열의 모든 구간 s[i:j]의 답을 알고 있다고 가정하여 s[0:L-1]의 답을 찾는 동적계획법을 활용해야 한다. 동영상 강의를 통하여 도움 설명을 할 예정이다.